package codetop.microsoft.T208;

/**
 * @Author: 18362
 * @Create: 2022-08-15 9:02:55 星期一
 */
class Trie {

    private int[] dict = new int[26];
    private Trie[] child = new Trie[26];

    public Trie() {

    }

    public void insert(String word) {
        insert(word, 0);
    }

    private void insert(String word, int cur) {
        int idx = word.charAt(cur) - 'a';
        if (cur == word.length()-1) {
            dict[idx] = 2;
            return;
        }
        if (dict[idx] == 0)
            dict[idx] = 1;
        if (child[idx] == null)
            child[idx] = new Trie();
        child[idx].insert(word, cur+1);
    }

    public boolean search(String word) {
        return search(word, 0, false);
    }

    public boolean startsWith(String prefix) {
        return search(prefix, 0, true);
    }

    private boolean search(String word, int cur, boolean isStartWith) {
        int idx = word.charAt(cur) - 'a';
        if (dict[idx] == 0)
            return false;
        if (cur == word.length()-1) {
            if (!isStartWith && dict[idx] == 1)
                return false;
            return true;
        }
        if (child[idx] == null)
            return false;
        return child[idx].search(word, cur+1, isStartWith);
    }
}
